% This example An LaTeX document showing how to use the l3proj class to
% write your report. Use pdflatex and bibtex to process the file, creating 
% a PDF file as output (there is no need to use dvips when using pdflatex).

% Modified 

% HELPER FUNCTIONS
% \input{figures/alice} << This is the best way to include a diagram, which are stored in the 'figures' folder. JD 
% \CITE{FALVO} where FALVO was the identifier of the required citation in dissertation.bib


\documentclass{l3proj}
\usepackage{hyperref}
\usepackage{pifont}
\usepackage{placeins}
\begin{document}
\title{String Search Algorithm Animation}
\author{John Dennis\\
	Hristo Georgiev \\
	David McBrierty \\
	Andrei Palade\\
	Marco Sarconi\\
	Garry Sharp \\
	}
\date{\today}
\maketitle
\begin{abstract}

\textit{The concept of string search algorithms in the field of Computing Science is a very important one, so it is crucial that undergraduates studying a related degree have a full understanding of these algorithms.}

\textit{There is no doubt that traditional teaching methods (such as the pseudcode of an algorithm itself, diagrams illustrating each step etc) are capable of achieving this. But one way to improve on these methods is through the use of animation, which can give students a better understanding of the flow of an algorithm and enable a student to visualise the algorithm more effectively.}

\textit{Our project is focused on the implementation of an animation tool specifically designed to help teach string search algorithms to students studying the Algorithmics 3 module at the University Of Glasgow. We aim for our application to improve on the weaknesses of similar tools we have researched, and also include some extra features which can help aid teaching even further.}

\end{abstract}
\educationalconsent
\newpage
\section*{Acknowledgements}
We would like to thank Dr. Gethin Norman for his invaluable support and advice over the course of the project. \\
We would also like to thank all of the students that took part in the evaluation of the system.\\
Finally we would like to thank Dr. Jeremy Singer and Dr. Tim Storer for the content provided in the concurrent PSD3 course which has been paramount to the production of this document.
\section*{Declaration}
We declare that the following document and associated implementation represents our own work except where otherwise stated.
\tableofcontents
%==============================================================================
\chapter{Introduction}
\label{intro}

\section{Preliminaries}
\label{prelim}

\begin{itemize}
\item{ An understanding of the string and substring concept}
\item{ How variables are used in the algorithm}
\end{itemize}

During our third year of Computing Science at the University of Glasgow, we have been introduced to string search algorithms.

A string is simply a combination of two or more characters (individual numbers, letters or symbols), and the algorithms we have studied are used to search over these strings to try and locate smaller strings (sub-strings) e.g. searching for the word "And" in "Andrew".

Analysing strings for sub-strings is a very useful concept to be familiar with in Computing Science, demonstrated by the many aspects of computing which make use of string search algorithms (searching for a website using a keyword in Google, for example).

Therefore, it is very important for Computing Science students to have a thorough understanding of string search algorithms, as they will need to apply this knowledge in various fields when they have graduated and are working.

In the dissertation the \textbf{sub-string} being found in a string will be referred to as the \textbf{pattern} and the \textbf{string} itself will be referred to as the \textbf{text}. In the "Andrew" example described earlier, "Andrew" is the text and "And" is the pattern.
Note that n will be defined as length of the text and m as the length of the pattern.
%------------------------------------------------------------------------------

\section{String Search Algorithms}

There are many string search algorithms, each one works in a different way and has its own 
advantages and disadvantages which have to be taken into consideration according to the 
circumstances they are used in.
\\
The string search algorithms that are implemented in our animator are the algorithms taught to us in Algorithmics 3; Brute Force \cite{bruteforce}, Knuth-Morris-Pratt \cite{kmp:1977} and Boyer-Moore \cite{boyermoore:1977}.
(note that \textbf{n} is the length of the \textbf{text} (the longer string we are searching \underline{through}), and \textbf{m} is the length of the \textbf{pattern} (the smaller string we are searching \underline{for}).


% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\subsection{Brute Force algorithm (Naive search)}

The brute force algorithm checks all positions in the text between 0 and $n-m$, regardless of whether an occurrence of the pattern starts there or not. It then shifts the pattern by exactly one position to the right after each attempt.
\\
The brute force algorithm requires no pre-processing, and a constant amount of extra space in addition to the pattern and the text. During the searching phase, the text character comparisons can be done in any order. The time complexity of this searching phase is $O(mn)$ and the expected number of text character comparisons is $2n$.\\

\underline{Advantages}
\begin{itemize}
\item{No pre-processing is required.}
\item{Is less complicated than the other algorithms}
\item{Can be almost as fast as the more complex algorithms}
\end{itemize}

\underline{Disadvantages}
\begin{itemize}
\item{Input text must be buffered}
\item{It takes some unnecessary small steps which could be skipped}
\item{Inefficient for small alphabets}
\end{itemize}

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

\subsection{Boyer-Moore algorithm}

The Boyer-Moore algorithm scans the pattern from right to left when proceeding through the text.
It then works out the most efficient next shift, by choosing between two pre-processing strategies. Its average-case complexity is $O(n/m)$, while the worst-case complexity is $O(nm)$.

\underline{Advantages}
\begin{itemize}
\item{Performs well on longer search strings.}
\end{itemize}

\underline{Disadvantages}
\begin{itemize}
\item{Can suffer poor performance when searching smaller strings.}
\item{Requires pre-processing.}
\end{itemize}

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

\subsection{Knuth-Morris-Pratt algorithm (KMP)}

The KMP algorithm works similarly to Brute-Force but does not backtrack over the string in the same way. This algorithm requires pre-processing but can be extremely efficient, which is shown by its $O(n)$ worst-case complexity.

\underline{Advantages}
\begin{itemize}
\item{Can be extremely efficient with its linear worst case complexity.}
\item{No buffering of scanned text is required.}
\item{Never needs to move backwards in the text, which is useful for pre-processing large files.}
\end{itemize}
\underline{Disadvantages}
\begin{itemize}
\item{More chances of mismatches occur when the alphabet is bigger.}
\item{Requires pre-processing.}
\end{itemize}

%------------------------------------------------------------------------------

\section{Research}

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

\subsection{Animations as a teaching tool}

From personal experience, string search algorithms can be quite a difficult concept to grasp. The process makes use of different variables to track the progress of the algorithm, and without proper images of the algorithm's steps in action it is hard to both visualise and keep track of the constantly changing values stored in these variables. These values correspond to the positions of the text and pattern and their relative position to each other. The understanding of an algorithm can, of course, be helped by the use of diagrams representing each step in the algorithm.\\
\\
However, as much as diagrams can give a good insight into the state of an algorithm at a certain point in time, they can sometimes struggle to illustrate the flow of the algorithm: the transition from each step to the next.\\
\\
An animation of the algorithm is a useful way to tackle this problem. An animation is split into frames, and each frame in the animation can represent a single state of the algorithm. As an animation transitions frame by frame, a student viewing it will be able to 
see how the algorithm process flows through step by step. To get a better idea of how effective algorithms are in teaching concepts to students, we 
researched some journals which analysed the success of animations used to demonstrate molecular modelling in chemistry.\\
\\
Researchers have found that animations help students better understand dynamic molecular processes \cite{Kelly&Jones:2005}.\\
Chemistry is a different subject from string search algorithms, but we feel that molecular animations and string search algorithms are similar as they aim to illustrate flowing and dynamic processes.\\
\\
Molecular behaviour is comprised of a series of steps, and the transfer from one step to another can gradually become complex and hard to follow.
This can often be the case with string search algorithms, and so analysing animations helping to teach a concept with such similar characteristics can lead to some relevant answers when questioning our tool's effectiveness in teaching.\\
\\
An interesting point raised by \cite{Simpson:2005}, was that today's students use their home 
computers for gaming more than for educational purposes. This was the result of a study 
conducted in the USA.\\
\\
Although the result of the study itself probably is not surprising, we can deduce that computer 
and video animation is part of a student's everyday life in some way or another. 
Subconsciously, they have an expectation of an educational environment that includes the 
nuances of the technical environment such as multimedia and complex interactivity.\\
So by living up to these expectations, and providing education in the form of animation with 
interactive control, an effective teaching tool can be developed for students \cite{Squire&Giovanetto&Devane&Shree:2005}.\\
\\
A couple of points to note about animations are:
\begin{itemize}
	\item{That they are only effective if provided with clear explanations \cite{Tversky:2001}}.
	\item{They do help considerably; although some content may be missed during the animation should the animation continue to play before the user has fully understood one teaching point \cite{Falvo:2008}.}
\end{itemize}

To make our animation tool effective we will address these two issues by:

\begin{itemize} 
	\item{Including textual explanations at various steps in the algorithm.}
	\item{Providing a play button, pause button, refresh button (starts from the beginning again) and a rewind button which goes back a step in the algorithm.}
\end{itemize}

The only problem that was found in a study conducted by Martin and Tversky \cite{Martin&Tversky:2003}, was that 
in the case of molecular animation, students sometimes misconstrued the colour of each 
molecule in the animation as being the colour of each molecule in real life.\\ 
\\
However, with our animator we do not have to worry about a problem like this, the colour of the objects in our animator can be selected arbitrarily, provided the overall colour scheme of the animator is set out in an objective, consistent and relevant manner. An example of this is when we use traffic light colour coding when text and patterns are being compared; we represent mismatching characters as red, characters which are processing as yellow and characters which match as green.

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

\subsection{Similar applications}


We feel that an algorithm animator application could greatly benefit future undergraduate 
students learning about string search algorithms. Our opinion has been justified by our own 
experience of using similar applications found on the internet, which have proven to be very 
capable of enhancing our understanding of string search algorithms.

Here are the online applications we analysed which animated the same algorithms as us:
\begin{itemize}
\item{\textbf{Brute Force Animator 1997, by Christian Charras and Thierry Lecroq, IGM} \cite{igm:1997}}
	\begin{itemize}
	\item[\ding{51}]{Animation offers good control with the ability to suspend and resume the animation.}
	\item[\ding{51}]{Able to reset animation back to first step.}
	\\
	\item[\ding{55}]{Restricted to one algorithm only.}
	\item[\ding{55}]{Not aesthetically pleasing, text being searched is very small.}
	\item[\ding{55}]{Unable to control speed of the animation, which by default is a little too fast.}
	\item[\ding{55}]{Unable to go back or forward by one step or several steps.}
	\end{itemize}

\item{\textbf{Boyer Moore Illustrated v2.0, by B Doyle} \cite{bmillustrated:2000}}
	\begin{itemize}
	\item[\ding{51}]{Able to reset animation back to first step.}
	\\
	\item[\ding{55}]{Restricted to one algorithm only.}
	\item[\ding{55}]{Text being searched is rather small.}
	\item[\ding{55}]{Colour is not used.}
	\item[\ding{55}]{Unable to go back a step in the algorithm.}
	\item[\ding{55}]{Cannot let the algorithm go step by step automatically (i.e 'Play' button).}
	\end{itemize}

\item{\textbf{String Searching, by Jiang Zheng, University of Pittsburgh} \cite{stringsearching:2006}}
	\begin{itemize}
	\item[\ding{51}]{Able to choose between Boyer-Moore and KMP.}
	\item[\ding{51}]{Displays some useful background information.}
	\item[\ding{51}]{Colour used well.}
	\\
	\item[\ding{55}]{Flow of steps is too fast.}
	\item[\ding{55}]{Unable to pause the animation.}
	\end{itemize}
\end{itemize}

We wish to create an improved application by implementing features incorporating the advantages of the above animation tools, while making sure it doesn't suffer from their disadvantages.

%------------------------------------------------------------------------------

\section{Project Plan}

%------------------------------------------------------------------------------

Providing an animation of an algorithm is a powerful way to aid the teaching of algorithms, but 
the animation still has to be constructed in a user-friendly, informative and accurate way.
Having analysed existing string search algorithm animators, we have recognised that animations of 
string search algorithms are powerful, but we feel these could still be improved upon.
There is certainly the opportunity to expand on previous efforts and provide an application 
with additional features capable of illustrating vividly the way string search algorithms operate. These 
additional features are as follows:

\begin{itemize}
	\item{Two separate views of an algorithm, one zoomed in to focus on the pattern in 
relation to the text, the other zoomed out and displaying all of the text.}
	\item{Animator runs at different speeds, according to the user's preference.}
	\item{Enable the user to pause the animation at any step.}
	\item{Go back a step in the algorithm when paused.}
	\item{Go forward a step in the algorithm when paused.}
	\item{View pseudo-code for the algorithm, highlighting the line of the current step in the algorithm.}
\end{itemize}

The two views of the strings and the view of the pseudo-code will all be resizeable, giving the 
user the ability to tweak the interface according to their preference.
A key aspect of the project will be to ensure all the different views of the same state in a given 
algorithm are in synchronisation and match up.

The following plan (Figure \ref{fig:tasklist}) is essential in ensuring the project is well organised. It takes into consideration certain milestones for which we must have completed specific tasks, as well as examination and holiday dates. There sometimes may appear to be small gaps in between tasks and milestones, but this is to allow us more time in situations where the team is depleted (e.g. if a team member is absent due to illness).

\begin{figure}[!h]
\includegraphics[width=16.5cm]{figures/task_list.png}
\caption{List of Tasks and Milestones}
\label{fig:tasklist}
\end{figure}

\begin{figure}[!h]
\includegraphics[width=18cm]{figures/gantt_semester1_crop.png}
\caption{Gantt Chart for Semester 1}
\label{fig:gantt1}
\end{figure}

\begin{figure}[!h]
\includegraphics[width=16cm]{figures/gantt_semester2_crop.png}
\caption{Gantt Chart for Semester 2}
\label{fig:gantt2}
\end{figure}

%==============================================================================
\chapter{Design}

\label{design}

In order to design the system to a high standard and to one which the client was happy with it was necessary to carry out thorough requirements gathering and analysis.

The original problem description was short and did not contain the level of detail required to have an in depth understanding of the functions the system should perform, instead it provided a overview of the system:

\begin{quotation}
``The aim of this project will be to build a system which can be used to animate/visualise the steps of string search algorithms. The potential algorithms include those for:
\begin{itemize}
\item{Brute Force}
\item{Knuth-Morris-Pratt}
\item{Boyer-Moore}
\end{itemize}
as well as their variants. As the motivation of the tool is to aid students with the understanding of the algorithms, the interface should be aimed at achieving this and also provide information on the different algorithms (and depending on progress comparisons between the algorithms).\cite{UniversityOfGlasgow:2011}'' 
\end{quotation}

Through further discussions and interviews with the client, the team was able to collect and analyse the requirements of the system, separating them into functional and non-functional, respectively.

\section{Functional requirements}

The functional requirements document should provide the functionality and the required behaviour of the system. Moreover, carefully capturing and documenting requirements, whose division was based on the \textit{MoSCoW method}\cite{Sommerville:2011}, provided a contractual agreement between the client and team on the functionality the system. The complete MoSCoW diagram is shown below for reference.
\begin{itemize}
\item{Must have}
\item{Should have}
\item{Could have}
\item{Would like to have}
\end{itemize}

\begin{figure}[!h]
\begin{center}
\includegraphics[width = 10cm]{figures/moscow.png} 
\end{center}
\caption{MoSCoW Diagram}
\label{fig:MD}
\end{figure}

Separating the requirements based on priority allowed the team to begin implementing and prototyping crucial components of the system and, consequently, return to features that had been deemed less important at a later stage.

As the team followed the waterfall model for software development, the requirements gathering was iterative, which led to the continuous refinement and revision based on input received from the client\cite {Hickey&Davis:2003}.
However, we felt that it was essential to gather and document as many system requirements as possible in the early stages of development in order to avoid possible problems or conflicts later.

\section{Non-functional requirements}
Non-functional requirements describe constraints and qualities that the system should have by nature. In contrast to functional requirements gathering, this type of requirements is harder to gather\cite{Malan&Bredemeye:2001}.
By analysing the non-functional requirements and giving them due consideration, we hoped to improve the overall system. The most important non-functional requirements that we gathered are listed below.
\begin{itemize}
\item{The system should have an interface which is user-friendly and easy to use.}
\item{It should present its animation and data in a manner which is educational and beneficial to the user.}
\item{The system should also be portable and maintainable.}
\item{The system code should be readable and the internal structure of the system should offer some level of extendibility for other developers or students.}
\end{itemize}

\section{System Scope}
The system scope outlines what is expected by the system: what functionality it should have and what functionality it should not have.

{\bf What the system should do:}
\begin{itemize}
\item{The system should provide facilities to both insert a pattern and a text, as well as the ability to select an algorithm whose execution process the user wants to examine. This should be based on an input form with text fields to insert the required details and a list of algorithms. In addition, two buttons, namely a start animation button and an exit the application button should be included.}
\item{The views should be moveable and resizeable}.
\item{The system should provide a visualisation of the text and pattern as boxes through the following five views (which are all technically internal frames):
	\begin{itemize} 
	\item{Firstly, a \textit{Full-box view} where the user can see the whole text and analyse a portion of the pattern box, 	positioned below the text box.}
	\item{Secondly, a section view of the previous view where the user can analyse the comparisons between characters of the pattern and text in detail.}
	\item{Thirdly, a \textit{Pseudocode view}, synchronised with the progress of the animation states. The pseudocode line which corresponds to the current position in the algorithm should be highlighted.}
	\item{The fourth view should control the animation progress in terms of pausing, interrupting, playing and resetting the animation states. Two separate functions which provide the functionality of going forward or backward in the animation progression should be supplied, as well as the ability to control the speed of the animation.}
	\item{The fifth view, which should be effectively a \textit{Pre-processing table view}, should be only visible whenever required by the currently chosen algorithm. For instance, the Knuth-Morris-Pratt and Boyer-Moore algorithms (utilising a border table and a skip table, respectively) employ this view, whereas the Brute-force algorithm does not.}
	\end{itemize}}
\item{The system must support three string search algorithms: Brute-force, Knuth-Morris-Pratt, and Boyer-Moore.}
\item{The system should allow the user to control the animation progress through play, pause and step forward/backward functionalities.}
\end{itemize}

{\bf What the system should not do:}
\begin{itemize}
\item{The system should not allow the algorithm to be changed from within the main application window. Instead, the user should select \textit{File->Start} and start over.}
\end{itemize}

\section{System Actors}  

There is only one actor for this system, namely the user. We have assumed that the user has been introduced to the algorithms previously (i.e. possesses the required background knowledge) as this system is aimed mainly at computing science students and lecturers. Therefore, we have automatically assumed that the user also possesses some basic computer skills, and additional differentiation between student and staff, i.e. introducing them as separate actors whose interaction approach to the system would differ fundamentally, was not necessary.

\section{Use Cases}

A use case describes an interaction between an external actor and the system and so documents in a readable form the functionality that the system provides\cite{Sommerville:2011}. Consequently, our uses cases were abstracted from the functional requirements the team had collected at previous stages.

The diagrams below shows all possible interactions the user (actor) can perform with the system. The use case were sub divided into sections-based on the aspect of the system the user would interact with: control, initialisation, information and views.

\begin{figure}[!h]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=5cm]{figures/usecase1}
\caption{Views}
\label{fig:UseCase: Views}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=5cm]{figures/usecase2}
caption{Initialisation}
\label{fig:UseCase: Initialisation}
\end{minipage}
\end{figure}

\begin{figure}[!h]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=5cm]{figures/usecase3}
\caption{Control}
\label{fig:figure1}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=5cm]{figures/usecase4}
caption{Initialisation}
\label{fig:figure2}
\end{minipage}
\end{figure}
\FloatBarrier

Two example use cases are shown below:
\\
\resizebox{18cm}{!}{
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{2}{|c|}{Start Use Case}\\\hline
\hline
Use case & Start\\\hline
Description & User enters text, pattern and selects an algorithm \\\hline
Rationale & The system must allow the selection of different algorithms and the user to enter their own text/pattern to be searched
 \\\hline
Priority& Must have \\\hline
Status& Implemented\\\hline
Actors& User \\\hline
Conditions& Post: The text and pattern is displayed, the selected algorithm is used.\\\hline
Risks& User may enter text which contains characters which could cause string errors, i.e control characters.\\\hline
User Interface& User Interface Pop-up window-InputFrame.Java \\\hline
Activity Diagram& \includegraphics[width=10cm]{figures/AD.png}\\\hline
\end{tabular}
}
\\
\\
\\
\resizebox{18cm}{!}{
\begin{tabular}{|l|l|l|}
\hline
\multicolumn{2}{|c|}{Change Speed Use Case}\\\hline
\hline
Use case & Change Speed.\\\hline
Description & The user can speed up or slow down the animation.\\\hline
Rationale & The animation progress should be controlled by the user. \\\hline
Priority& Must have \\\hline
Status& Implemented\\\hline
Actors& User \\\hline
Conditions& Post: The speed of the animation is changed.\\\hline
Risks& User Allowing for speeds which are too fast, or too slow. Speed may be effected by the users machine performance. \\\hline
User Interface& MainFrame.java \\\hline
\end{tabular}
}

Further information on the system requirements and uses cases are detailed in the requirement specification document\cite{TEAM-L:2011}.

\section{System Design}

Before the implementation stage commenced, it was imperative to design the overall view of the system and the exact mapping of requirements into working functionalities.

{\bf High level design}

The system implements the \textit{Model-View-Controller} design pattern\cite{Reenskaug:1978}. It allows for separation of concerns between the animation engine, the animation states and the algorithms.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/mvc.png}
\end{center}
caption{Model-View-Controler Diagram}
\label{fig:MVC}
\end{figure}

We followed a top-down design methodology: the system was broken into high-level components in order to gain an overall design insight. There followed a further breakdown of each component into a separate subsystem\cite{Wirth:1971}. It became apparent that there would be two main components of the back-end system: the algorithms which when run provide animation states and the animation engine which accesses these animation states in order to display the algorithm animation to the user.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/struct.png}
\end{center}
\caption{FSM high level structure}
\label{fig:structure diagram}
\end{figure}

{\bf The algorithms}

In order to make it easier for future developers to add other string search algorithms, a decision to create an algorithm interface was explicitly made. The Boyer-Moore, Knuth-Morris-Pratt and Brute-force all implement this interface as would any future algorithm do. By providing an interface and specifying the required methods and return values, a developer with a good understanding of the desired algorithm (which would effectively be a new addition), its states and how its pseudocode should be highlighted as the animation progresses, should be able to implement a new algorithm in a reasonable amount of time with a reasonable amount of effort spent.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/algorithmclass.png}
\end{center}
\caption{Algorithm Interface}
\label{fig:Algorithm Interface}
\end{figure}

{\bf Animation states}

An animation state represents an atomic operation that an algorithm performs at any given instant during its execution process. Any relevant data will then be needed for representing this operation as a part of the globally-running animation. Each animation state must contain the following information:
\begin{itemize}
\item{The starting position in the text.}
\item{The current position of the pattern.}
\item{The line of pseudocode which represents this operation.}
\item{The current highlighted text character.}
\item{The current highlighted pattern character.}
\item{A boolean variable, indicating whether the current pattern character and current text character match (i.e. holding a \texttt{true} or a \texttt{false} value, respectively).}
\end{itemize}


{\bf Computing the animation states}

In order to compute all animation states for the algorithms, we opted to first pre-run the entire algorithm and store the states before the system's main window actually appears to the user. This approach had some advantages over running the algorithm in real time:
\begin{itemize}
\item{It is easier to step forward and, in particular, backward through the animation states.}
\item{It avoids complex concurrency issues.}
\item{It maintains a separation of concerns: the animation engine deals only with a list of states provide.}
\end{itemize}

However, the disadvantage of this approach was a potential increment in the application initial loading time when the preprocessing actually takes part. We felt that this disadvantage is negligible but in order to avoid unnecessary processing (and, thus, poor performance in regard to system loading time) we limited the search text and search pattern to lengths of 40 and 20 characters, respectively.

{\bf The animation engine}

The animation engine provides a functionality to create and move the animation through its predefined states. It implements various UI components and allows the user to control the animation flow. 

\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/FSM.png}
\end{center}
caption{FSM diagram}
\label{fig:FSM}
\end{figure}


{\bf The System as a whole}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=10cm]{figures/class.png}
\end{center}
\caption{Class Diagram}
\end{figure}
 \FloatBarrier
\section{Interface Design}

As the system was designed to primarily act as an educational tool, it was crucial that this was emphasised on whilst designing its interface. The client required that the application must show two different viewpoints of the algorithm animation with supplementary pseudocode for the selected algorithm.

The overall design was kept simple, while polished intuitively by following standard design principles and heuristics\cite{Molich&Nielsen:1990}.

The system was designed to be visually pleasing and at the same time be substantial enough as an educational tool. This gave the direction of focus: demonstrate explanatory content rather than flashy animations or features.

\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{figures/wireframe.png}
\end{center}
\caption{Wireframe of views}
\label{fig:wireframe}
\end{figure}

\textbf{Customisation of windows}

A functionality of resizing each of the four views (or, otherwise, internal frames) is provided, on the basis that different users learn in different ways, and that one may wish to give priority to the window which is found most beneficial to the understanding of the algorithm.

Similarly, it is possible to hide windows from view. This functionality further allows the user to focus attention on areas of the system which that are found most useful.

\textbf{Control Panel}

The control panel provides the user's main interaction with the overall system and it was therefore crucial that this panel was made easy and intuitive enough to understand. The symbols used for play, pause, and move forward/backward were chosen due to their universal nature. In addition, there are buttons for swapping the Full-Box view and Section view, resetting, as well as a slider that controls the animation speed. Although we believe that the control panel buttons to be self-explanatory to users, we also provided tooltips (small snippets of information that appear when the cursor hovers over the button) which provide supplementary information about the functionality of the corresponding button.

\textbf{Pseudocode}

The pseudocode panel displays the pseudocode for the selected algorithm. As this system was mainly designed to be a teaching tool for the \textit{Algorithmics 3} class at the University of Glasgow, the client requested that the pseudocode provided by the application matched exactly the pseudocode provided in the course materials.

The panel also shows which line of code the animation is currently executing, by highlighting it. This is particularly important because it helps users to further understand the way the selected algorithm works by synchronising animation and corresponding pseudocode\cite{Robling&Freisleben:2000}.

\textbf{Animation}

A major consideration was how to represent the text and pattern within the system, as these are central to the animation and the overall feel of the application. Various ways of representing the text had been discussed in the early stages of design, but the ultimate decision was to represent both text and pattern by letters placed within boxes. We felt that this allowed the user to clearly identify single characters and follow the animation more easily.

As the algorithm progresses, the pattern moves further through the text in order to represent the algorithms position. One character from the pattern, along with its surrounding box, is aligned with one character from the text.

Another important consideration in terms of interface design was the state colouring: a \textit{mismatch}, \textit{currently processing} and a \textit{match}. It was decided that a mismatch should be represented within a red box, currently processing - within a yellow box and a match - within a green one. These colours were chosen as they are generally linked to good, bad and ready \cite{Birren:2006}.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=15cm]{figures/colour.png}
\end{center}
\caption{Comparison of text and pattern}
\label{fig:comp}
\end{figure}

As documented in the specification requirements\cite{TEAM-L:2011}, the client had requested that the system should show multiple views of the animation, in the interest of helping students visualise and understand the algorithms. We implemented two views of the algorithm animation:

\textbf{String-Box display}

The \textit{String-Box display} shows a zoomed-in view of the algorithms animation, allowing the user to focus on the current state of the animation. By default, this display is the larger of the two animation windows. However, it is possible to switch places with the \textit{Full-Box display} when desired.
\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/stringboxdisplay.png}
\end{center}
\caption{String Box}
\label{fig:string-box}
\end{figure}

\textbf{Full-Box display}

The \textit{Full-Box display} shows the string to be searched in its entirety, as well as the pattern. This allows the user to gain an overall view of the algorithms progress.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=10cm]{figures/fullbox.png}
\end{center}
\caption{Full Box}
\label{fig:fullbox}
\end{figure}

\textbf{Start Box}

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{figures/startbox.png}
\end{center}
\caption{Start Box}
\label{fig:startbox}
\end{figure}


The \textit{Start} dialog-box is the user's first point of contact with the system and which led to its simple and self-explanatory design. It is this exact place where the user enters the desired text to be searched through, the desired pattern to be searched for, and the algorithm of choice.

Based on the user-feedback results, we included a 'generate' button, which generates random text and pattern (note that the text may or may not contain the generated pattern). The idea behind this was to eliminate the repetitive task of entering a text and a pattern over and over again.

%==============================================================================
\chapter{Implementation}
\label{impl}

In this chapter, we describe our implementation of the algorithm animations.

\section{Overview}
The tool builds upon a skeleton formed by a set of pseudo code and practical examples, accompanied by step-by-step explanations, in the manner they were presented within the Algorithmics 3 course.\\

Initially, textual-based representations of the supported algorithms (namely Brute-Force, Knuth-Morris-Pratt, and Boyer-Moore) were implemented, in order to test basic functionality and interaction.\\

Consequently, a Graphical User Interface (GUI) was developed whose main design goals were to be kept as simple and clear as possible, while still providing a substantial amount of information to aid the educational process and the better understanding of the algorithms. Moreover, the tool was implemented in such way that it allows further extensibility and support for additional algorithms.\\

%------------------------------------------------------------------------------
\section{User Interface}

Implementation of the User Interface involved building each of the interface componenets seperately, before bringing them together into a single frame.

As a team, we felt that this approach to the user interface implementation would be the most apropriate, as it would enable us to divide the work involved in implementation easily.

In order to give the user control over the size of each componenet and also give them the ability to minimise each component, each component has been implemented to extend the JInternalFrame class (http://docs.oracle.com/javase/6/docs/api/javax/swing/JInternalFrame.html).  This allow us to give the necessary controls to the user for each componenet by providing arguments to the superclass constructor.

Each component that makes up the user interface is briefly described below, along with any implementation decisions that we feel are of note.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% PSEUDO CODE FRAME
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Psuedo Code Frame}
During the design stage, the team had agreed that would load the psuedo code for each algorithm in from a file stored within the projects directory structure.  This descision was primarily taken so that it would help towards making our tool extendable (which we would later, due to time constraints, be postponed for future development).  Loading the psuedo code from a file would enable users who wish to extend the tool able to easily include pseudo code for their algorithm with very little changes to the code (it is as simple as providing the filename to the constructor of the pseudo code, providing the file is in the appropriately named directory in the project directory structure).

The PseudoCodeFrame class (stored in /src/animationEngine/PseudoCodeFrame.java) also provides methods which support highlighting a given line of code, highlighting the next and previous line of the pseudo code and also clearing the highlighted line so that there are no lines highlighted.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% ANIMATION CONTROLS FRAME
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Animation Controls Frame}
The Animation Controls Frame (stored in /src/animationEngine/AnimationControlsFrame.java) is the frame that displays the buttons to the user that allow them to play, pause, step forwards, step backwards and reset the animation.  This frame also contains the slider bar that is used to set the speed that the animations plays at when the tool is playing through the animation, and also the button to swap the views of the animation round.

In order to support the portability of our software, each of the images used to represent the buttons is provided in the projects directory space, and each one is loaded in approriately when the constructor of the class is called.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% STRING BOX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{String Box}
The String Box class is implemented to display both the text and the pattern on the screen (each in a seperate StringBox).  Each StringBox is implemented so that it allows various highlighting methods which are detailed below.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=15cm]{figures/stringBoxHighlighting.png}
\end{center}
\caption{String Box Highlighting Methods}
\label{fig:String Box Highlighting Methods}
\end{figure}

The String Box class provides the software with all the methods required when highlighting the characters in an animation.

In our software we use String Boxes in two different display components (namely StringBoxDisplay and FullStringBoxDisplay - these displays are explained further below), and these displays call the highlighting methods of the StringBox class as they are required.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% STRING BOX DISPLAY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{String Box Display}
The String Box Display class (stored in /src/animationEngine/StringBoxDisplay.java), is the component that displays the text and pattern at a set size.

It contains two String boxes (one for the pattern and one for the text being searched), and this class handles the movement of these String Boxes within our software.

If a small piece of text is being searched through in our software, the String Box Display will move only the pattern.  This will only occur if the algorithm can be completed inside the default size of the String Box Display.

When a large piece text is being searched in our software, the pattern stops moving when it passes the middle of the StringBoxDisplay component it is in.  As the algorithm continues, the text itself begins to scroll to the left so that the relevant area that is being used in comparisons is viewable to the user.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% FULL STRING BOX DISPLAY
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{Full String Box Display}
The Full String Box Display handles the other display component in our User Interface.  It again contains two StringBoxes (one for the pattern and one for the text being searched for).

The Full String Box Display is used to display the entire text in its given size by resizing the String Boxes appropriately.

This can lead to the text and pattern becoming difficult to read in the case where a large piece of text is being searched, however we still feel that the Full String Box Display can be useful for guaging the algorithms progress over a large piece of text.  Due to the set size of the String Box Display it can sometimes mean that the start and end of the text are not visible in the String Box Display, the Full String Box Display then enables the user to quickly and easily locate the current position of the pattern.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% PRE PROCESSING TABLE FRAME
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{Pre Processing Frame}
The Pre Processing Frame is used for the implementations of the Boyer-Moore and Knuth-Morris-Prat pre processing stage.  Each of the algorithms requires the construction of a special data structure (different for each algorithm variation), and this extra frame is implemented in this class (stored in /src/animationEngine/PreProcessingFrame.java).

Despite the differences in these data structures, we have encapsulated both of them in a pre processing frame.  This frame supports the use of String Boxes and also a textual area for providing some information about the preprocessing stage to the user.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% ALGORITHMS AND ANIMATIONS STATES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Algorithms and Animation States}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% ANIMATION STATES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{Animation State}
In order to approach the task of display a complete animation to the user, our software would have to be able to handle each animation on a frame by frame basis.  In order to do this, our software contains a structure called an Animation State (stored in /src/animationEngine/AnimationState.java).

This Animation State class contains all off the relevant information that is required to display a single frame of an algorithm animation.  The variables we used to do this are given below.\\

\begin{figure}[h!]
\begin{center}
\includegraphics[width=10cm]{figures/animationState.png}
\end{center}
\caption{Animation State Variables}
\label{fig:Animation State Variables}
\end{figure}

Having built this class, we further extended the idea of an animation to become a list of these states.  By using a list structure of these states, we can greatly simplfy the task of displaying an animation by just keeping track of an index into this list (representing the currently displayed animation state).  This is the approach that our team took when implementing our software.  The only drawback from this approach is that at some stage the list will have to be built, which may become quite a time consuming task (ie if we are dealing with a large piece of text and a pattern that does not exist in the text).  However, given the limits we have imposed on the text and pattern length (40 characters and 20 characters respectively), the building of this list takes very little time and can be done without any hit of performance of our program.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% ALGORITHMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection{Algorithms}
In order to tie in with the idea of generating a list of AnimationStates each time our software has to run an algorithm, our software has to provide the method to build this list.  To do this, we have implemented an interface called Algorithm (stored in /src/algorithms/Algorithm.java).  The details of this implementation are given in the figure below.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=10cm]{figures/algorithmInterface.png}
\end{center}
\caption{Algorithm Interface}
\label{fig:Algorithm Interface}
\end{figure}

Each Algorithm that is supported by our software must be in a class that implements this interface.  The getStates method should fully execute the algorithm from start to finish, building an appropriate list of AnimationStates as it is processed.

This idea also helps towards making our tool extendable, however it would require a user with sufficient Java programming experience to be able to read and understand our software.

Due to the information we have stored in an AnimationState, constructing these AnimationStates can be done quite easily using the index that the algorithm naturally uses.  Below is the code excerpt for the Brute Force Algorithm that our software uses.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=15cm]{figures/BruteForceAlgorithm.png}
\end{center}
\caption{Brute Force Algorithm Implementation}
\label{fig:Brute Force Algorithm Implementation}
\end{figure}

This method will execute the algorithm as normal, building an Animation State for each pseudo code line, and give each Animation State the correct information for the current character being processed in both the text and the pattern.

\section{Development}

\section{Technologies used}

Various technologies, programming languages and frameworks were considered for the system implementation. However, in the end we decided to use the following technologies to be used throughout the development stages of our project:
\begin{itemize}
\item{the Java programming language}
\item{the Java Swing GUI widget toolkit}
\item{the integrated development environments (IDEs) Eclipse and NetBeans}
\item{the Subversion version control tool for Eclipse}
\end{itemize}

\subsection{The Java programming language}
While selecting a language for to implement the system, the team identified some criteria that the language must meet in order to be usable in a most effective way:
\begin{itemize}
\item{Familiarity: The team should have already had a working knowledge of the language or at least some substantial familiarity. Choosing a completely unfamiliar language would present further unnecessary challenges thoughout the development cycle.}
\item{Portability: It was advantageous that the system could be eventually used across multiple operating systems without having to developing separately for each.}
\item{Object-oriented: The language should have been object-oriented, as this is the programming style that the team was most familiar with.}
\item{Fast development: due to time constraints imposed on the project, the development time was short and the team required a language which could be used for rapid development.}
\end{itemize}

Given this criteria, the team was able to narrow down the implementation language to the following options:
\begin{itemize}
\item{Python}
\item{Java}
\item{C++}
\end{itemize}

\textbf{Java}: Java was developed by Sun Microsystems in 1995\cite{Byous:1998} and is an object-oriented programming language which offers extreme portability due to its use of a virtual machine\cite{JVM}. It is also a language which the team is very familiar with.

\textbf{Python}: Python was developed by Guido van Rossum in the late 1980s\cite{Rossum:2009}. It is a high-level language which allows for object-oriented programming. It provides rapid development facilities due to its simplistic syntax and excellent readability. It is also a language which is familiar to the team. However, we are not so highly-experienced in using Python, when taking in consideration our experience in Java.

\textbf{C++}: C++ was developed by Bjarne Stroustrup at Bell Labs in 1989\cite{Stroustrup:2012}. It extends standard C to provide classes and support for object-oriented programming\cite{Stroustrup:1997}. The language is powerful, fast and extremely popular. Some members of the team were already familiar with C++ while others had had foundations in C which would provide a basis to grasp the additional features of C++. However, the team felt that learning the advanced features of C++ would slow down the development process drastically.

After discussing the possible implementation language the team opted for Java programming language because it numerous advantages:
\begin{itemize}
\item{Extremely portable}
\item{Extensive libraries}
\item{Extreme familiarity}
\item{Excellent IDE support}
\item{Quick turnaround time}
\end{itemize}

Overall development was carried out on personal computers supporting the Linux operating system, while regular testing was also performed on Windows and Mac OSX machines.

\subsection{The Java Swing GUI widget toolkit}
The Java Swing toolkit was extensively used throughout the entire development process and the resulting overall look of our algorithm animator tool conforms to the common Swing UI design patterns. 

\subsection{Eclipse and NetBeans}
Eclipse was utilised as the primary development environment for our project. Having studied its usage extensively throughout the level 2 Java Programming and Object-Oriented Software Engineering courses, it was the most straightforward and reasonable choice in our case, having in mind that our primary choice of programming language had already been made.

\subsection{the Subversion version control tool for Eclipse}
The Subversion control tool has various advantages, which were particularly useful in our case, over its major competitors, Git and CVS:
\begin{itemize}
\item{can check out separate sub-trees, and not necessarily the entire development tree (which was extremely useful for working on the tool's implementation and the dissertation at the same time without introducing any conflicts in the overall process}
\item{much more flexible}
\item{provides a 'status' feature}
\item{provides all differences between the various repository versions in a colour-coded manner}
\end{itemize}

%==============================================================================
\chapter{Evaluation}
 
\section{Testing}
 
After we implemented the main functionality of the animator we started  the testing process in order to check if there are any flaws in our system.  Apart from the main part of the program, the rest was tested as it was built. For example the Swing components were visually analysed as the implementation progressed. Each of the following steps will describe the steps undertaken to achieve this.
 
\subsection{Unit Testing}
 
The purpose of the unit testing is to test individual modules of the system. In Java, this relates to a single method. The tests are being carried out by developers and their purpose is to check the internal logic and data flow of the newly written procedure. This type of testing is also known as white-box testing.
In order to execute this tests, we built a temporary framework around the module so the code can be executed and its internal workings viewed and assessed.
 
\begin{figure}
\begin{center}
\includegraphics[width=10cm]{figures/sample_test.png}
\end{center}
\caption{Sample Test}
\label{fig:Sample Test}
\end{figure}
 
Unit tests are created in order to give confidence about the correctness of one module, despite the fact that this particular module might depend on other modules. Test are required to check that the modules are required to check that are working correctly when they are interconnected or independent.
 
 
\subsection{Integration testing}
 
The integration testing was carried similar to the unit one. The difference in this instance was that the framework used was the one we used for developing our animation states for the system. Using this technique we managed to test the framework with the given algorithms. We were able to observe the results throughout testing.
For example: the getStates(String text, String pattern) can be found as both interconnected and independent.  For the Brute Force class this methods works independent from other modules. This behaviour occurs because Brute Force is not building an exterior table where as the other two algorithms depend on on exterior method: setUpBorderTable(int[] p).
 
Due to the approach taken for the unit and integration tests, no documentation was created. Additionally, as the system was developed the amount of interconnections between modules grew significantly. These two factors inevitably mean that some of the interconnections will not have been fully tested . Although, we managed to minimize the impact of having a defect in our system by creating print out stubs and testing each method as the implementation progressed.
 
\subsection{System Testing}
 
System testing attempts to use the final system as a main environment in all possible ways a user might interact with the product. The reason for doing this is to agree that the system will respond to the user's responses in the required manner. The full test plan can  be found in the appendix. This is divided into 3 sections, each corresponding to one algorithm.
 
\section{Design Evaluation}
 
The way in which we decided to tackle the testing of the system design (with regards to the GUI) is through the use of Nielsen's Heuristics \cite{Molich&Nielsen:1990}.
 
Nielsen's heuristics are widely regarded as the best set of heuristics when it comes to system user interface design. Below we explain each of his heuristics along with how this has been applied to our system.
 
\subsection{Visibility of system status}
The visibility of the system status is made abundantly clear throughout the use of the system. When the algorithm is playing the left and right toggle buttons are greyed out and the algorithm is put in an obvious state of current animation due to the movement and automatic change of highlighting.
 
When the system reached a terminated state, a message box containing a message conveying success or failure of the search is displayed.
 
When the algorithm is in a paused or stopped state the forward and backward toggle buttons are in an enabled state and so it is clear that the algorithm is not playing.
 
\subsection{Match between system and the real world}
As the system is designed to teach string search algorithms, it is sometimes difficult to not use jargon, especially when the algorithms themselves feature in the teaching of jargon (such as a border or skip table). After our user evaluation a few things were changed however. Amongst these the words 'text' and 'string' on the input box were changed to 'scannable text' and 'search pattern' in an attempt to avoid confusion.
Other than this, tool tips are implemented and we have endeavoured to ensure that everything that the user interacts with is intuitive (such as the control panel). This was reflected in our user evaluation feedback/think-aloud in which users stated that they were able to confidently use the system with no instructions.
 
\subsection{User control and freedom}
With regards to the users control of the algorithm animation, the user is given complete control with the exception that the speed must be set to a value between 1 – 10 and that an error message is given if the user tries to go forward/backwards too many steps (to a step that doesn't exist).
When the algorithm is changed the most recently used scannable text and search pattern strings are automatically inserted into the text boxes. If the user exits the system then they are presented with a JOptionPane which asks if the user is sure they wish to quit and then acts upon the response accordingly.
 
\subsection{Consistency and standards}
Users should not have to wonder whether different words, situations, or actions mean the same thing. Follow platform conventions.
The following aspects of the system are standardised and don't change:
\begin{itemize}
\item{The font used.}
\item{The pseudocode for each algorithm displayed in the panel (eg. The Boyer-Moore pseudocode doesn't change depending on the size of input).}
\item{The size of the boxes in the section view.}
\item{The colours used to highlight the pseudocode panel.}
\item{The colours used within the algorithm engines, these are:}
\begin{itemize}
\item{Red for mismatch, }
\item{Green for match, }
\item{Yellow for in a state of computation, }
\item{Blue for a border table shift (KMP only).}
\end{itemize}
\end{itemize}
The following aspects of the system are not standardised (semi-standardised):
\begin{itemize}
\item{The size of the boxes in the full view (dependant on user input).}
\item{The order in which elements are highlighted (dependant on user input).}
\item{The time taken for the algorithm to complete (dependant on user input via the speed changer and also on computer CPU clock speed).}
\item{The outcome of each algorithm (successful/unsuccessful dependant on user input).}
\end{itemize}
 
\subsection{Error prevention}
Error messages should be expressed in plain language (no codes), precisely indicate the problem, and constructively suggest a solution.
The system provides suitable error messages (in the form of a pop up message box) for each of the following eventualities:
\begin{itemize}
\item{The backwards/forward buttons are pressed when at the start/end of a string respectfully.}
\item{The scannable text that is entered by a user exceeds 40 characters.}
\item{The length of the search pattern entered by the user is greater than the length of the scannable text.}
\end{itemize}
To circumvent the issue of a user pressing the backwards/forwards buttons whilst the code is playing, the buttons are immediately greyed out (the click action is disabled).
 
\subsection{Recognition rather than recall}
The entire program is menu driven. The only instance in which it takes arguments (for the scannable text and search pattern) ensures that the text entered does not exceed 40 characters. Also if the user wishes to change the algorithm applied to this text they may do so as the system remembers it and automatically fills in the input text boxes on the input screen when the user clicks 'new'.
 
\subsection{Flexibility and efficiency of use}
There are two primary ways in which the system can be used. The first is by a student wanting to revise the algorithms in question or to learn them for the first time. The second is by a lecturer or teacher that wants to use the system during classes to demonstrate how the algorithms work to a class of students. We have designed and implemented the system mostly with the former in mind, however, we intend to design and implement a 'presentation mode' in future revisions of the software.
 
\subsection{Aesthetic and minimalist design}
Dialogues should not contain information which is irrelevant or rarely needed. Every extra unit of information in a dialogue competes with the relevant units of information and diminishes their relative visibility.
We have a series of resizeable windows that appear in our program (four or five depending on the algorithm being viewed) and so essentially the user is in control of the layout of the GUI themselves, we also provide a series of default layouts and sizes that the user can choose from to save them the trouble. Depending on how you view each window depends on how minimalist it is, whilst there is a lot of extra space with nothing in it in some of the windows, there is also a lot happening once the algorithm starts to animate (three windows each having its contents animated as a default). The user can toggle some of these views on or off as they see fit.
 
\subsection{Help users recognize, diagnose, and recover from errors}
We were not able to induce any errors in the system when we tested it with users. This is due to the limited input that a user can give the system. All sections of the code that can be deemed “error prone” (such as problems with finding the images for icons in a corrupt .jar file) are either surrounded by try/catch blocks (a common method of dealing with error prone areas in java) or with a print statement prints an explanation of the error to the terminal/command line.
 
\subsection{Help and documentation}
Javadoc documentation is provided along with a user manual which provided a basic walkthorough of the system. User evaluation showed that due to the nature of the program (teaching string search algorithms) that our target user base will be quite computer literate. In addition to the software being quite intuitive to use we do not envisage that the system will cause anyone any difficulty with regards to its use.
 
\section{User Evaluation}
 
The process of user evaluation is extremely important in the software development cycle. The purpose of our user testing plan was to find bugs in the system that we had not been aware of and also to see in which ways the software could be improved in order to increase its usability.
 
Our evaluation and testing of the system has been a continuous process. Throughout the implementation stage we have evaluated out own design as well as allowed the client to test various components of the system and gather feedback on them. This has ensured that the final system does not feature unreliable components or components that do not function according to the client's demands. This relatively iterative process has led to the generation of many revisions of the system via the SVN control system.
 
When were testing the system on end users, there were still a few known bugs present. Therefore, any feedback regarding the fixing of these bugs has been omitted from this section. Full feedback forms are presented in the appendix.
 
The manner in which we tested the software consisted of hybrid test comprising of both questionnaire and think-aloud methodologies conducted at the same time. The users were first read an introduction/briefing script which explained that the questionnaire and think-aloud evaluation was entirely voluntary, and the users would not be presented with any abnormal risks. Moreover, they were let to know that they could stop participating at any time they wanted. They were then instructed to fill in sections one and two of the questionnaire (which are sample control questions and prior-knowledge questions respectively). The user was then given the chance to interact and experiment with the various features of the program and talk with us. Whilst they were doing this, we made sure that they were able to complete each of the tasks outlined in section three of the questionnaire.
 
The final section of the questionnaire is by far the most important when it comes to re-analysing the system from a user's perspective.
 
\subsection{DECIDE Framework}
 
Before developing and implementing an evaluation test (such as a questionnaire or interview), we decided to use the DECIDE framework. This frameworks ensures that the planning of the evaluation stage is conducted in the best possible manner. Each of the six stages of the DECIDE framework is explained below along with what we did for each one.
 
\textbf{1. Determine the Goals}
 
The first stage in our evaluation plan consisted of firstly gaining an understanding of what exactly our evaluation wanted to achieve. Obviously one of the main reasons that any system is thoroughly tested is to aid in finding bugs that had not previously been found. If bugs aren't found at this point it does not mean that bugs don't exist rather that the testing on this occasion has not managed to find them. In addition to searching for bugs we also wanted to gather general feedback and opinions from potential users to find out what they liked/disliked, how effective the animation system was (by contrasting understanding before and after) and also in which ways they would improve the system if they were given the chance.
 
\textbf{2. Explore the Questions}
 
In order to achieve the correct results as defined by our goals, it is very important to ensure that the correct questions are asked. These could be broken down into three sections. The first being identifying information, the purpose of which was simply to see how well suited the user would be to using the system. It was quite a short section and asks briefly about their educational background and their experience with algorithms.
 
The second section was designed to build on the first section (in the sense to gaining a more in depth understanding of the student's relationship with the algorithms concerned) as well as provide us with some quantitative analysis about their understanding of the algorithms before they use the system.
 
The final section is the sections that most interests us with regards to the evaluation of the system as it provides us with information regarding the system's success (when figures are compared to the figures gathered in section two) as well as providing qualitative information about how the system can be improved or changed.
 
\textbf{3. Choose Evaluation Approach and Methods}
 
The format of our user analysis consisted of a test which combined the methodologies of a questionnaire and think-aloud evaluation. This was achieved by issuing each participant with a questionnaire as well writing down any comments that they make whilst using the system. This also ensured that we gained a more accurate understanding of the participants real thoughts on the system as they may have perceived something that they said 'not worthy' of being included in the questionnaire. This approach was chosen due to its speed and ease of use (as the people that tested it were very busy) whilst also providing reasonably accurate data. It also allowed the team to view a typical interaction with the system and see how long it took for a typical user to do perform an action on the system.
 
\textbf{4. Identify the Main Practical Issues}
 
There are a number of issues involved when approaching the user evaluation from the angle described above, in addition to various issues related to this project in particular. A common issue with questionnaire and think-aloud evaluation methodologies alike is that you do not always get accurate information. People are much more likely to 'guess' the answer to a question or to approximate the answer to something similar is the question is not quite right. The way in which we decided to overcome this was to clearly explain what each question meant and to explain (and later during the testing reiterate) the importance of answering truthfully and succinctly, in addition to this it was of vital importance that all the the questions were worded clearly (we changed a few words to simpler words in an attempt to make the questionnaire more accessible for students with a limited understanding of English).
 
Another issue was the time and budget constraints that we had to add to adhere to (limited time for evaluation due to other university work and the sequence of events through which we arrived at the evaluation as well as a null budget). This was a large reason for our decision to use the questionnaire and think-aloud evaluation methodologies as it was easier and faster to prepare and execute a user test.
 
The final issue that we faced was that the target audience for this system was third year computer science students. This meant that not only was there a very limited number of people that were eligible for user testing, but also that many of the people that were eligible were peers. The way in which we decided to combat this was to reassure the participant that they should be completely honest in their evaluation as we would not be able to attribute the final completed questionnaire to them.
 
\textbf{5. Deal with ethical issues}
 
We first made sure that the experiment conformed to the ethical guidelines for experimentation outlined by the University of Glasgow. Each participant was read an introductory 'briefing' script before beginning the testing which explained what the experiment involved and that they may withdraw participation without excuse at anytime. Likewise, a debreifing script concluded each evaluation which detailed what the experiment intended to prove and that their responses would be help anonymously. We gave each participant a copy of our contact details and told them that we would provide them a copy of the final dissertation at their request.
 
\textbf{6. Evaluate, Analyse and Interpret the Data}
 
Full data analysis (both quantitative and qualitative) can be found below.
 
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{figures/brute.jpg}
\end{center}
%\caption{Brute Force}
\label{fig:bruteforce}
\end{figure}
 
\begin{center}
\textit{The brute force user evaluation shows that users were generally either very comfortable with the algorithm before with an equal or slightly greater understanding after, or that the users had little or no understanding before and had a very hight level of understanding afterwards. This shows that the algorithm animator works well as it is able to teach the algorithm to people who have a limited understanding whilst no confusing perople who already understand how the algorithm works.}
\end{center}
 
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{figures/bm.jpg}
\end{center}
%\caption{Boyer-Moore}
\label{fig:boyermoore}
\end{figure}
 
\begin{center}
\textit{From the Boyer-Moore graph above, we can see that the average understanding before the use of the system was 2.29 out of 10, after the use of the system the average rating was 5.86. This equals an average gain of 3.57 out of 10 (more than a double increase). The reasons why the understanding levels are not higher are attributed to a number of things. Firstly, the amount of time that each student was given was limited. Secondly, there were still some minor bugs with the highlighting of some elements in the section and full views.}
\end{center}
\newpage
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{figures/kmp.jpg}
\end{center}
%\caption{KMP}
\label{fig:kmp}
\end{figure}
 
\begin{center}
\textit{Looking at the KMP graph above we can see that the average level of understanding of the algorithms before using the system was 1.71 out of 10, after the use of the system this increased to 4.86 out of 10 showing a 3.14 out of 10 mark increase. Although the number when viewed as a percentage (almost 33\%gain), the numbers are not as high as we would like. This again is attributed to the lack of time the users had as well as highlighting difficulties. Although one user pointed out that they weren't paying attention. We imagine that this user was testing how well the system operated as opposed to how well they could learn the algorithm. This may have created a slight accuracy discrepancy with regards to the results.}
\end{center}
 
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm]{figures/avg.jpg}
\end{center}
%\caption{Average}
\label{fig:average}
\end{figure}
 
\begin{center}
\textit{Overall the results seems encouraging in the sense that the algorithm animator achieves its goal in increasing its user's understanding of how the algorithms concerned function and operate. Ideally we would have liked the post testing numbers to be higher (around 8 as opposed to the current 6.57), however, we are confident that implementation of a few of the ideas expressed below along with user's using the system in a less hectic environment will achieve better results.}
\end{center}
\newpage
 
\small\addtolength{\tabcolsep}{-5pt}
    \begin{tabular}{|p{4cm}|c|c|c|c|c|c|c|c|}
\hline
Algorithm&Part.1&Part.2 & Part.3 & Part.4 & Part.5 & Part.6 & Part.7 & Avg (Mean) \\
\hline
Brute Force Before & 10 & 9 & 7 & 9 & 2 & 1 & 1 & 5.57 \\
Brute Force After & 10 & 10 & 10 & 10 & 5 & 10 & 8 & 9 \\
\hline
Boyer-Moore Before & 6 & 1 & 2 & 2 & 1 & 1 & 3 & 2.29 \\
Boyer-Moore After & 9 & 3 & 6 & 6 & 2 & 10 & 5 & 5.86 \\
\hline
Knuth-Morris-Pratt (KMP) Before & 3 & 1 & 1 & 2 & 1 & 1 & 3 & 1.71 \\
Knuth-Morris-Pratt (KMP) After & 7 & 6 & 6 & 3 & 2 & 5 & 5 & 4.86 \\
\hline 
Average Algorithm Understanding Before & 6.33 & 3.67 & 3.33 & 4.33 & 1.33 & 1 & 2.33 & 3.19 \\
Average Algorithm Understanding After & 8.67 & 6.33 & 7.33 & 6.33 & 3 & 8.33 & 6 & 6.57 \\
\hline
\end{tabular}
 
\begin{center}
\textit{The above table shows the information related to graphs above in numeric fors}
\end{center}
 
\subsection{Paraphrased Questionnaire Answers.}
 
\underline{Section 1. Information Quota Questions.}
 
\textbf{Are you a current student of Computer Science, Software Engineering, Mobile Software Engineering or any other related discipline?} - \textit{All answers were yes}
 
\textbf{Are you a student at the University of Glasgow, if no, where do you study?} - \textit{All answers were yes}
 
\textbf{Have you studied (to any degree) any of the following string search algorithms: Brute Force, Boyer-Moore, Knuth-Morris-Pratt?} - \textit{Majority answered yes for Brute Force, mixed yes/no responses for Boyer-Moore and Knuth-Morris-Pratt.}
 
 
\underline{Section 2. Pre-testing analysis}
 
\textbf{4. Realistically, would an animation program be something you would use when it comes to learning/revising algorithms?} - \textit{Everyone gave a positive response to this question, some saying that they would prefer it to traditional methods.}
 
\textbf{5. Have you ever used an animation program as a teaching tool before?} - \textit{Everyone gave a positive response in answer to this question.}
 
\underline{Section 4. Post use evaluation}
 
\textbf{5. Was there anything that surprised you or was different about the system from what you expected? If so what was it and was is good/bad. Please elaborate.} - \textit{The responses here were vastly varied and both positive and negative feedback was conveyed, some of which, as expected with user evaluation testing, contradicted itself. Negative feedback included:}
\begin{itemize}
\item{The KMP algorithm wouldn't run (problem with the Java Virtual Machine at the time of testing, problem now resolved).}
\item{The section view was at times difficult to read due to obstructions.}
\item{The algorithm explanations being 'too heavy' meaning that they were not succinct or clear enough for a novice to understand.}
\item{There was too much to look at whilst the algorithm is playing.}
\end{itemize}
\textit{Positive feedback included:}
\begin{itemize}
\item{The system as a whole was preferable to lecture slides.}
\item{That the pseudocode panel was a welcome addition to explaining the algorithms.}
\item{The system in general was very robust.}
\end{itemize}
 
\textbf{7. Is there anything extra that could be done to make the algorithms clearer or more understandable?} - \textit{The responses gathered here were extremely useful. Some of the suggestions had already been discussed and disregarded by the team for various reasons. Others had not been considered and minor revisions to the system were then discussed, some of there were:}
\begin{itemize}
\item{Better wording of the input frame text boxes.}
\item{Multiple lines of code when the scannable text exceeds 40 characters.}
\item{Slow down the animation.}
\item{Make sure that the search pattern boxes and scannable text boxes are aligned.}
\item{Show the variable names.}
\item{Window size should be calculated from the length of the scannable text string.}
\item{Descriptions of algorithms that are easier for novice users to understand.}
\end{itemize}
 
\textbf{8. What would you change (if anything) about the system?} - \textit{Lots of the responses given to this question were similar to the question above. Responses included:}
\begin{itemize}
\item{Being able to change the pattern without having to re-enter the string.}
\item{The system is close to perfect with a friendly GUI.}
\item{The functionality for the system to add random data.}
\item{A race algorithm feature. (meaning the ability to view the different algorithms working on identical data concurrently so that they can be contrasted).}
\item{An indication of which side of the speed slider is slow and which side is fast.}
\item{KMP algorithm crashed (same Java Virtual Machine error as described above).}
\end{itemize}
 
\textbf{9. General comments (anything relevant to the system/design is welcome here)} - \textit{Comments in this section included:}
\begin{itemize}
\item{Well-designed, robust system. Would be nice to see it used in lectures. }
\item{Easy to use without instructions. Pseudocode panel and stepping features were good features.}
\item{Highlighting the steps of the algorithms is a good feature.}
\end{itemize}
 
\subsection{Evaluation of User Testing Responses}
 
Most of the feedback that we collected seemed positive and encouraging. The main issues that were brought up were:
 
One of the features that was requested twice was that there is no limit on the size of the scannable text string which is entered and that to compensate, the program should move the algorithm onto multiple lines. This was something that we considered in the requirements stage and was not included as the assumptions section of our requirements document clearly highlights the fact that the system is not intended to perform actual searches and that input length should be 'reasonable' which we have defined as a maximum of 40 characters. This is due to the system's purpose being to teach students how the algorithms work and not to actually search for things. It is a likely possibility that either the students were struggling to add something for that section of the questionnaire or that they did not fully understand the purpose of the program.
 
Slowing down the algorithm was something that was mentioned by several people in the evaluation. This I think was mainly down to us using higher speeds due to our familiarity with the algorithms and also our implementation concerns with seeing the highlighting of items progress correctly and so did not slow the algorithm down sufficiently in the version of the software that we tested on other people. An implementation issue is that due to the Java Virtual Machine's own internal optimiser, part of the Just In Time (JIT) compiler, the program must be launched from the command line terminal in UNIX systems with the following flags 'java -Djava.compiler=NONE' which essential disables the JIT compiler and allows a constant speed to be used throughout the animation.
 
The race algorithm feature is something that we would have liked to do, however, the true speed of the algorithm as well as the complexity time as a function of $O(n)$ would not be reflected accurately due to us having to artificially reproduce the speed and conditions of the algorithms. This may even result in students becoming more confused by the algorithms.
 
\section{Improvements/Future Developments}
The ability to be able to revise, alter and release new versions of software is generally very important in the software development process for a number of reasons. Obviously, if an application is launched for commercial gain, developments and updates must be innovative in order to ensure that you are not overshadowed by competitors. From a more elementary perspective, as computers become more advanced (in the case of this project we are referring to graphics cards in particular), programs may appear sloppy if they do not make full use of the resources available to them.
 
As our project is university-based and not developed for commercial gain, it is unlikely that any actual future developments will be made as there are no plans for an actual launch (besides the eventual inclusion in the teaching process within one of the Algorithmics 3 lab sessions related to the study of string search algorithms). Nevertheless, we have developed a list of future development plan for any potential further versions of the software which are detailed below.
 
\subsection{Pre-User Testing}
From the very first meetings with our project supervisor, and during the requirements capture process, we developed a very loose list of requirements (i.e. without formal documentation) and began to order them by priority. From this, we were able to distinguish between what was a-must-have feature and what was a desirable feature. This was also the starting point for documenting a list of assumptions from the system.
 
Our team meetings and project plan reflected both our own and our project supervisor's take on how to go about designing and implementing the system in the best possible way. The requirements that were seen as desirable were now re-organised in a fashion that reflected both the estimated time to implement and usefulness. We arrived at an agreement that we should only start to implement these features after the essential functionality of the system functioned correctly. Various items on this list have now become part of the future developments plan.
 
\subsubsection{Further Development}
 
\textbf{Add functionality for adding custom algorithms} - \textit{This would have been a fantastic feature to include as it would make the learning process so much more universal. The semantics of adding this feature soon became apparent when the initial experimental implementation began. Due to the nature of having to create an animation, the creation of a custom interface between the animation display and algorithm syntax was insurmountable given the programming expertise of team members and time constraints on the system.}
 
\textbf{Ability to zoom in or our on section view} - \textit{This would have been a fantastic feature to include, however, the complexity of creating this to a high standard was not possible given the time constraints that we had for the production of this system. It is, however, very possible to implement and would be a very useful feature for a future version of this system}
 
\textbf{Smoother animation process} - \textit{The animation as it stands currently involves a JLabel (as part of a string box) rapidly changing between the various colour states. In future revisions we hope to be able to make the movement more fluid, perhaps haveing the highlighting 'slide' across to the right or have the colours fade in and fade out.}
 
\textbf{Addition of the Rabin-Karp algorithm} - \textit{Due to time constraints and the differences between the Rabin-Karp algorithm and the other algorithms, it was very difficult to implement this algorithm by the deadline for the first submission. It is however, entirely possible to do with addition time for implementation and evaluation.}
 
\subsection{Post-User Testing}
 
\subsubsection{Immediate Changes}
 
After we had completed our user evaluation, we decided to immediately change a few things that were mentioned by users in the evaluation. One of the main things that was raised by multiple users was that the animation engine needed to slow down (both its fastest and slowest speeds), this was a relatively easy issue to fix as it involved changing a constant within the implementaton that was used to determine the speed.
 
Another thing that was brought up was that it would be nice to have the text from one algorithm automatically enterned into the box if the user wanted to see a different algorithm applied to that text, this was also changed relatively quickly.
 
In addition to remembering previously entered text, we also created a button which would generate random text into the boxes.
 
The numbering on the initial speed bar was backwards (1 at the left was the fastest and 10 at the right was slowest). This was naturally the reverse of what you would expect from a speed bar so this was also changed.
 
Change the names of the formerly know 'text' and 'pattern' input boxes as this didn't offer sufficient description to novice users unfamiliar with the jargon. These were changed to read 'Scannable text' and 'Search pattern'.
 
\subsubsection{Additional Future Developments}
 
\textbf{Addition of a race feature} - \textit{The race feature would essentially be the ability to view two (or potentially all three) algorithms together executing on the same text string. This would involve a redesign of the current GUI or an additional view so that the screen did not look too cluttered. This could be achieve by having 1 animation control panel at the top with two section view and pseudocode panels divided horizontally and stacked on top of one another so that comparison between the algorithms can be seen.}
 
\textbf{Addition of presentation mode} - \textit{This was mentioned to us during the think-aloud evaluation. The idea is that the system could take an algorithm and animate it in a more presentation friendly way. Another way that this could be accomplished would be by adding functionality where an animation could be exported as a video or .gif file}
 
\textbf{Show complexity difference between various versions of the same algorithms} - \textit{Because the system is designed purely as a teaching tool to show how the algorithms work, this would have been a great feature to include in order to show the different ways in which the same algorithm could be implemented. However, when implementing the pseudocode panel it became difficult to illustrate the difference between the various forms of the algorithm (as the actual code is not displayed), attempts to do this actually lead to the algorithm animation becoming much more complicated to follow, therefore negating the general purpose of the system (that is to assist in understanding string search algorithms).}
 
\textbf{System to run as a web applet} - \textit{This was another think aloud idea that was suggested during our system presentation. Its biggest advantage would basically be that it would be much more accessable to others as it can be accessed via most web browsers. Java Swing was the most advantageous platform to develop the system on for the first version as all members of the team were well versed in the use of Java and we all had very limited knowledge of web technologies at the time of implementation.}


%==============================================================================
\chapter{Conclusion}

%==============================================================================
\section{Contributions}

Here we explain that Lewis Carroll wrote chapter \ref{intro}. John Wayne
was out riding his horse every day and didn't do anything. Marilyn Monroe
was great at getting the requirements specification and coordinating the
writing of the report. Betty Davis did the coding of the kernel of the
project, described in Chapter \ref{impl}. James Dean handled the
multimedia content of the project.

%==============================================================================

\bibliography{dissertation}
\bibliographystyle{plain}

\end{document}
